# include <bits/stdc++.h>

const int N=100010;


typedef long long ll;

int T;
std::set <ll> S;
const ll INF=1e18;

inline ll read(void){
	ll res,f=1;
	char c;
	while((c=getchar())<'0'||c>'9')
		if(c=='-') f=-1;
	res=c-48;
	while((c=getchar())>='0'&&c<='9')
		res=res*10+c-48;
	return res*f;
}

ll sum;

void print(ll x){
	if(x<0) putchar('-'),x=-x;
	if(x>9) print(x/10);
	putchar(x%10+'0');
	return;
}

namespace serious{
inline void init(void){
	int len=S.size();
	ll cur=0,ans=0;
	auto il=S.begin(); auto ir=S.rbegin();
	ll mn=0,mx=0;	
	for(int i=1;i<len;++i){	
		mn+=*il,mx+=*ir; ++il,++ir;
		if(mn>cur) ans+=mx-mn;
		else ans+=(mx-1)-cur;
		cur=mx-1;		
	}		
	printf("%lld\n",ans);
	return;
}	
}

namespace funny{
inline void init(void){
//	std::cerr<<"luangao is running"<<std::endl;
	
	int len=S.size();
	
	ll cur=0,ans=0;
	auto il=S.begin(); auto ir=S.rbegin();
	ll mn=0,mx=0;
	
	int ARI=0,NASHI=0;
	
	std::vector <int> vec;
	
	ll pmn=0,pmx=0;
	ll L=-1,R=-1;
	
	for(int i=1;i<len;++i){	
		mn+=*il,mx+=*ir; ++il,++ir;		
		if(mn>=pmx) ans+=pmx-pmn;
		else{
			L=pmn;
			break;
		}
		pmn=mn,pmx=mx;
	}
		
	if(L==-1){
		print(ans+pmx-pmn),puts("");
		return;
	}
	
	il=S.begin(),ir=S.rbegin();
	mn=mx=sum,pmn=pmx=sum;
	
	for(int i=len-1;i;--i){
		mx-=*il,mn-=*ir; ++il,++ir;
		if(i!=len-1&&mx<=pmn) ans+=pmx-pmn;
		else{
			if(i!=len-1){
				R=pmx-1;
				break;
			}
		}
		pmx=mx,pmn=mn;
	}
	print(R-L+1+ans),puts("");
	return;
}	
}



std::mt19937 rng(0);

inline int rd(int l,int r){
	return rng()%(r-l+1)+l;
}

int main(void){
	freopen("kte.in","r",stdin);
	freopen("kte.out","w",stdout);
	
	int T=read();
	
	int op=(T<=1000)?0:1;
	
	while(T--){
		ll x=read();
		if(S.count(x)) S.erase(x),sum-=x; else S.insert(x),sum+=x;
		if(op==0) serious::init();
		else funny::init();
	}

	return 0;
}

